PC Media 7/PC MEDIA CD07.iso/share/prog/cm/cmbintr.cpp

C/C++ Source or Header | 1994-09-06 | 10.6 KB | 414 lines

// CmBinTr.cpp
// -----------------------------------------------------------------
// Compendium - C++ Container Class Library
// Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
// -----------------------------------------------------------------
// Binary tree implementation.
// -----------------------------------------------------------------

#include <cm/include/cmbintr.h>


// "CmBinaryTree" is the tree copy constructor.
//
CmBinaryTree::CmBinaryTree(const CmBinaryTree& aTree)
{
  _root = NULL;
  copy   (aTree);
  balance();
}


// "~CmBinaryTree" is the tree destructor.
//
CmBinaryTree::~CmBinaryTree()
{
  removeAll();
}


// "=" assignment operator copies the contents of the specified tree
// into this tree.
//
CmBinaryTree& CmBinaryTree::operator=(const CmBinaryTree& aTree)
{
  if (&aTree != this)
  {
    removeAll();
    copy     (aTree);
    balance  ();
  }
  return *this;
}


// "add" adds the specified object to this tree.
//
Bool CmBinaryTree::add(CmObject* pObj)
{
  if (!pObj) return FALSE;

  CmBinaryTreeNode *newnode = new CmBinaryTreeNode(pObj);
  if (!newnode) return FALSE;

  if (!_root)                                // Tree is empty.  Add at root.
    _root = newnode;

  else                                       // Tree is not empty.
  {
    int               comp   = pObj->compare(_root->_data);
    CmBinaryTreeNode *rover  = (comp < 0) ? _root->_left : _root->_right;
    CmBinaryTreeNode *parent = _root;

    while (rover)                            // Search for vacant slot.
    {
      parent = rover;
      comp   = pObj->compare(rover->_data);
      rover  = (comp < 0) ? rover->_left : rover->_right;
    }

    if (comp < 0) parent->_left  = newnode;  // Add new node appropriately.
    else          parent->_right = newnode;
  }
  _size++;
  return TRUE;
}


// "remove" removes the first occurrence of an object that isEqual
// to the specified object from the tree.
//
Bool CmBinaryTree::remove(CmObject* pObj)
{
  if (!_root || !pObj) return FALSE;           // Exit if empty tree.

  CmBinaryTreeNode *rover  = _root;            // Init for search.
  CmBinaryTreeNode *parent = NULL;
  Bool              done   = FALSE;

  while (rover && !done)                       // Search for object.
  {
    int comp = pObj->compare(rover->_data);
    if (comp != 0)                             // Advance to next node.
    {
      parent = rover;
      rover  = (comp < 0) ? rover->_left : rover->_right;
    }

    else                                       // Object was found.
    {
      CmBinaryTreeNode *temp1 = rover;         // Save pointer to object.

      if (rover->_right == NULL)
        rover = rover->_left;

      else if (rover->_right->_left == NULL)
      {
        rover        = rover->_right;
        rover->_left = temp1->_left;
      }

      else
      {
        CmBinaryTreeNode *temp2 = rover->_right;
        while (temp2->_left->_left) temp2 = temp2->_left;
        rover         = temp2->_left;
        temp2->_left  = rover->_right;
        rover->_left  = temp1->_left;
        rover->_right = temp1->_right;
      }

      if (!parent)                             // Object to remove is root.
        _root = rover;

      else
      {
        comp = temp1->_data->compare(parent->_data);
        if (comp < 0) parent->_left  = rover;
        else          parent->_right = rover;
      }

      if (ownsObjects()) delete temp1->_data;  // Delete data if owned.
      delete temp1;                            // Delete node.
      _size--;
      done = TRUE;
    }
  }
  return done;
}


// "lookup" returns the first occurrence of an object which isEqual
// to the specified object.
//
CmObject* CmBinaryTree::lookup(CmObject *pObj) const
{
  if (!_root || !pObj) return NULL;

  CmBinaryTreeNode *rover = _root;
  CmObject         *ret   = NULL;

  while (rover && !ret)
  {
    int comp = pObj->compare(rover->_data);
    if (comp == 0) ret    = rover->_data;
    else           rover  = (comp < 0) ? rover->_left : rover->_right;
  }
  return ret;
}


// "contains" checks to see if an object that isEqual to the specified
// object exists in the tree.
//
Bool CmBinaryTree::contains(CmObject *pObj) const
{
  return (lookup(pObj) == NULL) ? FALSE : TRUE;
}


// "occurrences" returns the number of objects in the tree
// isEqual to the specified object.
//
unsigned CmBinaryTree::occurrences(CmObject *pObj) const
{
  unsigned             total = 0;
  CmBinaryTreeIterator iterator(*this);
  while (!iterator.done())
    if (pObj->isEqual(iterator.next()))
      total++;
  return total;
}


// "removeAll" removes all the objects from the tree.
//
void CmBinaryTree::removeAll()
{
  if (_root)
  {
    killNode(_root, ownsObjects());
    if (ownsObjects()) delete _root->_data;
    delete _root;
    _root = NULL;
    _size = 0;
  }
}


// "balance" balances the current contents of the binary tree.
//
void CmBinaryTree::balance()
{
  CmTQueue<CmBinaryTreeNode*> *que = new CmTQueue<CmBinaryTreeNode*>;
  CmBinaryTreeIterator iterator(*this);
  while (!iterator.done())
  {
    CmBinaryTreeNode *newnode = new CmBinaryTreeNode(iterator.next());
    if (newnode) que->push(newnode);
  }

  Bool owns = ownsObjects();
  if (owns) ownsObjects(FALSE);
  removeAll();
  if (owns) ownsObjects(TRUE);

  balanceHalf(que, 0, que->size() - 1);
  delete que;
}


// "newIterator" creates and returns a new tree iterator.
//
CmIterator* CmBinaryTree::newIterator() const
{
  return new CmBinaryTreeIterator(*this);
}


// "write" writes the tree contents to the specified reserve file.
//
Bool CmBinaryTree::write(CmReserveFile& file) const
{
  return CmContainer::write(file);
}


// "read" reads objects from the specified reserve file.
//
Bool CmBinaryTree::read(CmReserveFile& file)
{
  Bool success = CmContainer::read(file);
  if (success) balance();
  return success;
}


// "balanceHalf" is called recursively to balance part of the tree.
//
void CmBinaryTree::balanceHalf(CmTQueue<CmBinaryTreeNode*> *que,
                               int low, int high)
{
  if (low <= high)
  {
    int mid = (low + high) / 2;
    add(((*que)[mid])->_data);
    balanceHalf(que, mid + 1, high);
    balanceHalf(que, low, mid - 1);
  }
}


// "killNode" is a recursively called static function which takes a
// subtree and destroys the left and right branches.
//
void CmBinaryTree::killNode(CmBinaryTreeNode* subTree, Bool owns)
{
  if (subTree->_left)
  {
    killNode(subTree->_left, owns);
    if (owns) delete subTree->_left->_data;
    delete subTree->_left;
    subTree->_left = NULL;
  }

  if (subTree->_right)
  {
    killNode(subTree->_right, owns);
    if (owns) delete subTree->_right->_data;
    delete subTree->_right;
    subTree->_right = NULL;
  }
}


// "CmBinaryTreeIterator" is the constructor for the tree iterator
// class.
//
CmBinaryTreeIterator::CmBinaryTreeIterator(const CmBinaryTree &Tr)
                                           : _tree(Tr)
{
  _stack = new CmTStack<CmBinaryTreeNode*>;
  _node  = _tree._root;
  if (_node)
  {
    while (_node->_left)
    {
      _stack->push(_node);
      _node = _node->_left;
    }
  }
}


// "~CmBinaryTreeIterator" is the destructor for the tree iterator
// class.
//
CmBinaryTreeIterator::~CmBinaryTreeIterator()
{
  delete _stack;
}


// "next" returns a pointer to the object pointed to by the iterator.  The
// iterator is then advanced to the next node in the tree.
//
CmObject* CmBinaryTreeIterator::next()
{
  if (!_node) return NULL;                        // Iteration is over.

  CmObject* retValue = _node->_data;              // Save off object pointer.

  if (_node->_right)                              // If there is a right
  {                                               // branch, advance to it
    _stack->push(_node);                          // and descend all the way
    _node = _node->_right;                        // down it's left side.
    while (_node->_left)
    {
      _stack->push(_node);
      _node = _node->_left;
    }
  }

  else                                            // Otherwise, back up the
  {                                               // tree until we are back
    CmBinaryTreeNode* temp;                       // at the top or until we
    do                                            // are no longer a right
    {                                             // branch.
      temp  = _node;
      if (_stack->size() == 0) _node = NULL;
      else                     _node = _stack->pop();
    } while (_node && _node->_right == temp);
  }
  return retValue;
}


// "previous" returns a pointer to the current object and decrements
// the iterator.
//
CmObject* CmBinaryTreeIterator::previous()
{
  if (!_node) return NULL;                        // Iteration is over.

  CmObject* retValue = _node->_data;              // Save off object pointer.

  if (_node->_left)                               // If there is a left
  {                                               // branch, advance to it
    _stack->push(_node);                          // and descend all the way
    _node = _node->_left;                         // down it's right side.
    while (_node->_right)
    {
      _stack->push(_node);
      _node = _node->_right;
    }
  }

  else                                            // Otherwise, back up the
  {                                               // tree until we are back
    CmBinaryTreeNode* temp;                       // at the top or until we
    do                                            // are no longer a left
    {                                             // branch.
      temp  = _node;
      if (_stack->size() == 0) _node = NULL;
      else                     _node = _stack->pop();
    } while (_node && _node->_left == temp);
  }
  return retValue;
}


// "first" moves the iterator to the first object in the tree.
//
void CmBinaryTreeIterator::first()
{
  _stack->removeAll();
  _node = _tree._root;
  if (_node)
  {
    while (_node->_left)
    {
      _stack->push(_node);
      _node = _node->_left;
    }
  }
}


// "last" moves the iterator to the right most tree node thus
// pointing to the last object in the tree.
//
void CmBinaryTreeIterator::last()
{
  _stack->removeAll();
  _node = _tree._root;
  if (_node)
  {
    while (_node->_right)
    {
      _stack->push(_node);
      _node = _node->_right;
    }
  }
}